home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / networking / info-service / wais / ir-book-sources / bool / driver.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-04-08  |  10.5 KB  |  384 lines
  1. /***************************  driver.c  **************************************
  2.  
  3.   Purpose:    Test driver program for boolean operations code.
  4.  
  5.   Provenance:    Written and tested by S. Wartik, April 1991.
  6.  
  7.   Notes:    This module contains a main program and accompanying
  8.           subroutines that, when compiled, exercise every function
  9.         of the boolean operations module.  The testing is purely
  10.         in terms of the external interface that the boolean
  11.         operations module presents.  That is, the effects of
  12.         constructor functions are examined through the projector
  13.         functions.  This makes the code (almost) implementation-
  14.         independent.  For this reason, it may be used (with slight
  15.         modifications, controlled through #ifdef's) to test both
  16.         the bit-vector and the hashing implementations.
  17.         
  18.           Usage for the bit-vector version is:
  19.  
  20.             driver lower-bound upper-bound
  21.  
  22.         where the bounds specify the legal domain of the set.  In
  23.         the current implementation, abs(upper-bound - lower-bound)
  24.         must be less than 256.
  25.             
  26. **/
  27. #ifndef BIT_VECTOR_IMPL                /* Make the bit-vector    */
  28. #    ifndef HASHING_IMPL            /* implementation be    */
  29. #        define    BIT_VECTOR_IMPL        /* the default.        */
  30. #    endif
  31. #endif
  32.  
  33. #include    <stdio.h>
  34.  
  35. #ifdef BIT_VECTOR_IMPL
  36. #    include    "bv.h"
  37. #else /* HASHING_IMPL */
  38. #    include    "hash.h"
  39. #endif
  40.  
  41. #define N_SETS        3
  42.  
  43. #define MIN_ELEMENTS    5        /* Make the tests "interesting". */
  44.                     /* Require at least 5 elements.     */
  45. #ifdef HASHING_IMPL
  46. int    hash(key)            /* Define the hashing function   */
  47.     elementType    key;        /* as the sum of the squares of  */
  48. {                    /* each bit's magnitude, base 3. */
  49.     int    i;
  50.     int    threePower;
  51.     int    sum;
  52.  
  53.     threePower = 1;
  54.     sum = 0;
  55.     for ( i = 0; i < 8*sizeof(elementType); i++ ) {
  56.         register int    bitValue;
  57.         bitValue = (key & 01)*threePower;
  58.         bitValue *= bitValue;
  59.         sum += bitValue;
  60.         threePower *= 3;
  61.     }
  62.  
  63.     return sum;
  64. }
  65.  
  66. boolean compare(v1, v2)
  67.     elementType    v1, v2;
  68. {
  69.     return v1 == v2;
  70. }
  71. #endif
  72.  
  73.  
  74. void    Exit_If_Error_On();
  75. void    Exit_Indicating_Failed_Op();
  76.  
  77.  
  78. void    Test_Set_Operators();        /* The main routine is implemented  */
  79. void    Test_Union_Operators();        /* as a series of calls to several  */
  80. void    Test_Intersection_Operators();    /* procedures, each of which tests  */
  81. void    Test_Subtraction_Operators();    /* a particular aspect of the        */
  82. void    Test_Copy();            /* module.                */
  83. void    Test_Iterate();
  84.  
  85. boolean    Iterator();
  86.  
  87.  
  88. main(argc, argv)
  89.     int    argc;
  90.     char    *argv[];
  91. {
  92.     set    s[N_SETS];
  93.     int    lower, upper;
  94. #ifdef HASHING_IMPL
  95.     int    number_of_buckets;
  96. #endif
  97.     int    i;
  98.  
  99. #ifdef BIT_VECTOR_IMPL
  100.     if ( argc != 3 ) {
  101.         printf("Usage: %s lower-bound upper-bound\n", argv[0]);
  102. #else
  103.     if ( argc != 4 ) {
  104.         printf("Usage: %s lower-bound upper-bound number-of-buckets\n", argv[0]);
  105. #endif
  106.         exit(1);
  107.     }
  108.  
  109.     lower = atoi(argv[1]);
  110.     upper = atoi(argv[2]);
  111.     if ( upper < lower+MIN_ELEMENTS ) {
  112.         printf("Please specify a set that can contain at least %d elements.\n",
  113.                MIN_ELEMENTS);
  114.         exit(1);
  115.     }
  116. #ifdef BIT_VECTOR_IMPL
  117.     else if ( upper - lower > MAX_ELEMENTS-1 ) {
  118.         printf("This implementation can't accommodate upper-lower>%d.\n",
  119.                MAX_ELEMENTS-1);
  120.         exit(1);
  121.     }
  122. #else
  123.     if ( (number_of_buckets = atoi(argv[3])) <= MIN_ELEMENTS ) {
  124.         printf("The 1st argument must be an integer >= %d.\n",
  125.                MIN_ELEMENTS);
  126.         exit(1);
  127.     }
  128.     
  129. #endif
  130.  
  131.     for ( i = 0; i < N_SETS; i++ ) {    /* Test creation. */
  132. #ifdef BIT_VECTOR_IMPL
  133.         Create(lower, upper, &s[i]);
  134. #else
  135.         Create(number_of_buckets, hash, compare, &s[i]);
  136. #endif
  137.         Exit_If_Error_On("Create");
  138.     }
  139.     fputs("Creation works.\n", stdout);
  140.  
  141.     for ( i = 0; i < 2; i++ ) {        /* Test clearing sets. */
  142.         Clear(&s[i]);
  143.         Exit_If_Error_On("Clear");
  144.         if ( Empty(&s[i]) )
  145.             Exit_If_Error_On("Empty");
  146.         else    Exit_Indicating_Failed_Op("Empty");
  147.     }
  148.     fputs("Clearing works.\n", stdout);
  149.  
  150.     Test_Set_Operators(s, lower, upper);
  151.     fputs("Basic operators works.\n", stdout);
  152.     Test_Union_Operators(s, lower, upper);
  153.     fputs("Union works.\n", stdout);
  154.     Test_Intersection_Operators(s, lower, upper);
  155.     fputs("Intersection works.\n", stdout);
  156.     Test_Subtraction_Operators(s, lower, upper);
  157.     fputs("Subtraction works.\n", stdout);
  158.     Test_Copy(s, lower, upper);
  159.     fputs("Copying works.\n", stdout);
  160.     Test_Iterate(s, lower, upper);
  161.     fputs("Iterating works.\n", stdout);
  162.  
  163.     fputs("\nThe implementation passes.\n", stdout);
  164.     exit(0);
  165. }
  166.  
  167. void Test_Set_Operators(s, lower, upper)
  168.     set    s[];
  169.     int    lower, upper;
  170. {
  171.     int    i;
  172.     
  173.     for ( i = lower; i <= upper; i++ ) {    /* Test insertion of all    */
  174.         Insert(&s[0], i);        /* valid elements for a     */
  175.         Exit_If_Error_On("Insert");    /* set that doesn't already */
  176.         if ( Member(&s[0], i) )        /* contain them.        */
  177.             Exit_If_Error_On("Member");
  178.         else    Exit_Indicating_Failed_Op("Member");
  179.     }
  180.  
  181.     for ( i = lower; i <= upper; i++ ) {    /* Test insertion of all */
  182.         Insert(&s[0], i);        /* valid elements for a  */
  183.         Exit_If_Error_On("Insert");    /* set that already has  */
  184.         if ( Member(&s[0], i) )        /* them.         */
  185.             Exit_If_Error_On("Member");
  186.         else    Exit_Indicating_Failed_Op("Member");
  187.     }
  188.  
  189.     for ( i = lower; i <= upper; i++ ) {    /* Test deletion of all  */
  190.         Delete(&s[0], i);        /* valid elements when   */
  191.         Exit_If_Error_On("Delete");    /* the set already has     */
  192.         if ( ! Member(&s[0], i) )    /* them.         */
  193.             Exit_If_Error_On("Delete");
  194.         else    Exit_Indicating_Failed_Op("Member");
  195.     }
  196.  
  197.     for ( i = lower; i <= upper; i++ ) {    /* Test deletion of all  */
  198.         Delete(&s[0], i);        /* valid elements when   */
  199.         Exit_If_Error_On("Delete");    /* the set doesn't have     */
  200.         if ( ! Member(&s[0], i) )    /* them.         */
  201.             Exit_If_Error_On("Delete");
  202.         else    Exit_Indicating_Failed_Op("Member");
  203.     }
  204. }
  205.  
  206. void Test_Union_Operators(s, lower, upper)
  207.     set    s[];
  208.     int    lower, upper;
  209. {
  210.     int    i;
  211.  
  212.     Insert(&s[0], lower);            /* Test union of a set    */
  213.     Exit_If_Error_On("Insert");        /* with an empty set.      */
  214.     Unite(&s[0], &s[1], &s[2]);        /*   s2 <- {lower}U{}      */
  215.     Exit_If_Error_On("Unite");
  216.     if ( Member(&s[2], lower) )
  217.         Exit_If_Error_On("Member");
  218.     else    Exit_Indicating_Failed_Op("Member|Unite");
  219.     for ( i = lower+1; i <= upper; i++ )
  220.         if ( Member(&s[2], i) )
  221.             Exit_Indicating_Failed_Op("Member|Unite");
  222.         else    Exit_If_Error_On("Member");
  223.  
  224.     Insert(&s[1], lower+1);            /* Test union of two non-    */
  225.     Exit_If_Error_On("Insert");        /* empty, non-intersecting   */
  226.     Unite(&s[0], &s[1], &s[2]);        /* sets.             */
  227.     Exit_If_Error_On("Unite");        /*   s2 <- {lower}U{lower+1} */
  228.     if ( Member(&s[2], lower) && Member(&s[2], lower+1) )
  229.         Exit_If_Error_On("Member");
  230.     else    Exit_Indicating_Failed_Op("Member|Unite");
  231.     for ( i = lower+2; i <= upper; i++ )
  232.         if ( Member(&s[2], i) )
  233.             Exit_Indicating_Failed_Op("Member|Unite");
  234.         else    Exit_If_Error_On("Member");
  235.  
  236.                     /* Test union of two non-empty,   */
  237.     Insert(&s[0], lower+1);        /* intersecting sets.          */
  238.     Exit_If_Error_On("Insert");    /*   s2 <- {lower,lower+1} U      */
  239.     Unite(&s[0], &s[1], &s[2]);    /*        {lower+1}      */
  240.     Exit_If_Error_On("Unite");
  241.     if ( Member(&s[2], lower) && Member(&s[2], lower+1) )
  242.         Exit_If_Error_On("Member");
  243.     else    Exit_Indicating_Failed_Op("Member|Unite");
  244.     for ( i = lower+2; i <= upper; i++ )
  245.         if ( Member(&s[2], i) )
  246.             Exit_Indicating_Failed_Op("Member|Unite");
  247.         else    Exit_If_Error_On("Member");
  248. }
  249.  
  250. void Test_Intersection_Operators(s, lower, upper)
  251.     set    s[];
  252.     int    lower, upper;
  253. {
  254.     int    i;
  255.  
  256.     Clear(&s[0]);
  257.     Clear(&s[1]);
  258.  
  259.     Insert(&s[0], lower);            /* Test intersection of a */
  260.     Exit_If_Error_On("Insert");        /* set with an empty set. */
  261.     Intersect(&s[0], &s[1], &s[2]);        /*   s2 <- {lower}^{}      */
  262.     Exit_If_Error_On("Intersect");
  263.     for ( i = lower; i <= upper; i++ )
  264.         if ( Member(&s[2], i) )
  265.             Exit_Indicating_Failed_Op("Member|Intersect");
  266.         else    Exit_If_Error_On("Member");
  267.  
  268.     Insert(&s[0], lower);            /* Test intersection of two    */
  269.     Exit_If_Error_On("Insert");        /* non-empty, non-intersecting */
  270.     Insert(&s[1], lower+1);            /* sets.                  */
  271.     Exit_If_Error_On("Insert");        /*   s2 <- {lower}^{lower+1}   */
  272.     Intersect(&s[0], &s[1], &s[2]);
  273.     Exit_If_Error_On("Intersect");
  274.     for ( i = lower; i <= upper; i++ )
  275.         if ( Member(&s[2], i) )
  276.             Exit_Indicating_Failed_Op("Member|Intersect");
  277.         else    Exit_If_Error_On("Member");
  278.  
  279.     Insert(&s[0], lower);            /* Test intersection of two non- */
  280.     Exit_If_Error_On("Insert");        /* non-empty, intersecting sets. */
  281.     Insert(&s[0], lower+1);            /*   s2 <- {lower,lower+1}^         */
  282.     Exit_If_Error_On("Insert");        /*          {lower,lower+2}    */
  283.     Clear(&s[1]);
  284.     Insert(&s[1], lower);
  285.     Exit_If_Error_On("Insert");
  286.     Insert(&s[1], lower+2);
  287.     Exit_If_Error_On("Insert");
  288.     Intersect(&s[0], &s[1], &s[2]);
  289.     Exit_If_Error_On("Intersect");
  290.     if ( Member(&s[2], lower) )
  291.         Exit_If_Error_On("Member");
  292.     else    Exit_Indicating_Failed_Op("Member|Intersect");
  293.     for ( i = lower+1; i <= upper; i++ )
  294.         if ( Member(&s[2], i) )
  295.             Exit_Indicating_Failed_Op("Member|Intersect");
  296.         else    Exit_If_Error_On("Member");
  297. }
  298.  
  299. void Test_Subtraction_Operators(s, lower, upper)
  300.     set    s[];
  301.     int    lower, upper;
  302. {
  303.     int    i;
  304.  
  305.     Clear(&s[0]);                /* Subtract one empty set   */
  306.     Clear(&s[1]);                /* from another.        */
  307.     Subtract(&s[0], &s[1], &s[2]);
  308.     Exit_If_Error_On("Subtract");
  309.     for ( i = lower; i <= upper; i++ )
  310.         if ( Member(&s[2], i) )
  311.             Exit_Indicating_Failed_Op("Member|Subtract");
  312.         else    Exit_If_Error_On("Member");
  313. }
  314.  
  315. void Test_Copy(s, lower, upper)
  316.     set    s[];
  317.     int    lower, upper;
  318. {
  319.     int    i;
  320.     
  321.     Clear(&s[0]);                 /* Create a set with every */
  322.     for ( i = lower; i <= upper; i += 3 ) {     /* third possible value,   */
  323.         Insert(&s[0], i);         /* copy it, and make sure  */
  324.         Exit_If_Error_On("Insert");     /* both sets have the same */
  325.     }                     /* members.            */
  326.  
  327.     Copy(&s[0], &s[1]);
  328.  
  329.     for ( i = lower; i <= upper; i++ )
  330.         if ( Member(&s[0], i) != Member(&s[1], i) )
  331.             Exit_Indicating_Failed_Op("Member|Copy");
  332.         else    Exit_If_Error_On("Member");
  333. }
  334.  
  335. int    Count_Of_Elements_Iterated_Over;
  336.  
  337. boolean Iterator(e)
  338.     int    e;
  339. {
  340.     if ( e % 2 != 0 )    /* passed a value that wasn't inserted. */
  341.         Exit_Indicating_Failed_Op("Iterate");
  342.     Count_Of_Elements_Iterated_Over++;
  343.     return TRUE;
  344. }
  345.  
  346. void Test_Iterate(s, lower, upper)
  347.     set    s[];
  348.     int    lower, upper;
  349. {
  350.     int    i;
  351.     int    Count_Of_Elements_Added;
  352.  
  353.     Count_Of_Elements_Added = Count_Of_Elements_Iterated_Over = 0;
  354.  
  355.     Clear(&s[0]);
  356.     for ( i = (lower/2)*2 + 2; i <= upper; i += 2 ) {
  357.         Insert(&s[0], i);        /* Insert all even values */
  358.         Exit_If_Error_On("Insert");    /* (except perhaps the      */
  359.         Count_Of_Elements_Added++;    /* first) into the set.   */
  360.     }
  361.  
  362.     Iterate(&s[0], Iterator);
  363.     Exit_If_Error_On("Iterate");
  364.     if ( Count_Of_Elements_Added != Count_Of_Elements_Iterated_Over )
  365.         Exit_Indicating_Failed_Op("Iterate");
  366. }
  367.  
  368. void Exit_If_Error_On(operation)
  369.     char    operation[];
  370. {
  371.     if ( ! Error_Occurred() )
  372.         return;
  373.     printf("%s operation caused an error.\n", operation);
  374.     exit(1);
  375. }
  376.  
  377.  
  378. void Exit_Indicating_Failed_Op(operation)
  379.     char    operation[];
  380. {
  381.     printf("%s operation failed to function correctly.\n", operation);
  382.     exit(1);
  383. }
  384.